#ifndef _lib_binary_bit_util_h_
#define _lib_binary_bit_util_h_

/*

// http://www.ciphersbyritter.com/NEWS4/BITCT.HTM

// (C) Donald W. Gillies, 1992.  All rights reserved.  You may reuse
// this bitcount() function anywhere you please as long as you retain
// this Copyright Notice.
//
#define bitready()	register unsigned long tmp
#define bitcount(n) 							\
      (tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111),	\
      tmp = ((tmp + (tmp >> 3)) & 030707070707),			\
      tmp =  (tmp + (tmp >> 6)),					\
      tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077)

// 16 instructions on most risc machines for 32-bit bitcount !

main()
{
	bitready();

	printf("bitcount(1) = %ld\n", bitcount(1));
	printf("bitcount(2) = %ld\n", bitcount(2));
	printf("bitcount(3) = %ld\n", bitcount(3));
	printf("bitcount(0xff) = %ld\n", bitcount(0xff));
	printf("bitcount(0xffffff) = %ld\n", bitcount(0xffffff));
}

% ~/a.out
bitcount(1) = 1
bitcount(2) = 1
bitcount(3) = 2
bitcount(0xff) = 8
bitcount(0xffffff) = 24
%

Christian Bau wrote:
> There is no single instruction to count bits in a word on the PowerPC,
> only an instruction to count the number of leading zero bits. Written in
> C, the following code would be quite efficient on the PowerPC if you do
> the operation a lot:
> 
>    static unsigned char lookup_table [2048] = {
>       // Initialised to the number of bits in i for 0 <= i < 2048
>    }
> 
>    #define bit_count(n)    (lookup_table[((n)>>22) & 0x7ff]       \
>                            +lookup_table[((n)>>11) & 0x7ff]       \
>                            +lookup_table[((n)>> 0) & 0x7ff])
> 
> Total latency six cycles if a pointer to the lookup table is in a

A Pentium would be similar:

; assume input value in EAX

  mov ebx,eax
  and eax,7ffh

  mov ecx,ebx
  and ebx,7ffh SHL 11

  shr ecx,22
  mov eax,lookup_table[eax]

  shr ebx,11
  mov ecx,lookup_table[ecx]

  add eax,ecx
  mov ebx,lookup_table[ebx]

  add eax,ebx

*/
/* Count the number of bits in a word. */
inline int bit_count_simple(uint n)
{
	int result = 0;

	while (n != 0)
	{
		result += n & 0x00000001;
		n >>= 1;
	}

	return result;
}

namespace
{
	const int s_bit_count_lut[16] =
	{
		0,		// 0b0000
		1,		// 0b0001
		1,		// 0b0010
		2,		// 0b0011
		1,		// 0b0100
		2,		// 0b0101
		2,		// 0b0110
		3,		// 0b0111
		1,		// 0b1000
		2,		// 0b1001
		2,		// 0b1010
		3,		// 0b1011
		2,		// 0b1100
		3,		// 0b1101
		3,		// 0b1110
		4,		// 0b1111
	};
}

/* Count the number of bits in a word, using a lookup table for each 4 bit sequence */
inline int bit_count_lut(uint n)
{
	return
			s_bit_count_lut[(n      ) & 0x0000000f]
		+	s_bit_count_lut[(n >>  4) & 0x0000000f]
		+	s_bit_count_lut[(n >>  8) & 0x0000000f]
		+	s_bit_count_lut[(n >> 12) & 0x0000000f]
		+	s_bit_count_lut[(n >> 16) & 0x0000000f]
		+	s_bit_count_lut[(n >> 20) & 0x0000000f]
		+	s_bit_count_lut[(n >> 24) & 0x0000000f]
		+	s_bit_count_lut[(n >> 28) & 0x0000000f];
}

inline int bit_count(uint n)
{
	return bit_count_simple(n);
}

#endif